package com.chenyi.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author chenyi
 * @className MergeSorting
 * @date 2022/4/2 23:44
 */
public class MergeSorting {

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));
    }

    public static int[] sort(int[] sourceArray) {
        // 拷贝数组
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 判断当前数组是否拆分到最小值
        if (arr.length < 2) {
            return arr;
        }
        // 获取数组中间值
        int mid = arr.length / 2;
        // 获取拆分后左边数组
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        // 获取拆分后右边数组
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        return merge(sort(left), sort(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];

        // 左边数组下标
        int leftKey = 0;
        // 右边数据下标
        int rightKey = 0;
        // 返回数据下标
        int i = 0;
        while (rightKey < right.length && leftKey < left.length) {
            if (left[leftKey] <= right[rightKey]) {
                result[i++] = left[leftKey++];
            } else {
                result[i++] = right[rightKey++];
            }
        }

        while (leftKey < left.length) {
            result[i++] = left[leftKey++];
        }

        while (rightKey < right.length) {
            result[i++] = right[rightKey++];
        }

        return result;
    }

    public static int[] merge1(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }


}
